The invention relates generally to computer graphics and animation and more particularly to techniques for deforming or warping graphical objects.
Warping or deforming (the terms are used interchangeably) graphical models is an important operation in many areas of computer graphics. Deformation of planar curves is a basic operation in 2-D cartoon animation as well as in digital publishing. Surface and solid warping find widespread application solid and geometric model manipulation as well as 3-D animation. Many significant industries such as portions the entertainment industry and the medical imaging industry rely heavily on suites of computer graphics tools that include warping techniques.
There are many computer-implemented wraping techniques known in the art. Indeed, the literature is heavily populated with niche solutions to seemingly separate sets of problems. There is a need for a warping technique that addresses the general problems encountered in warp design and provides a general solution framework flexible enough, not only for warp designers to rapidly develop new warps, but also for them to achieve warp results comparable to the existing niche solutions when desired. Such a general solution technique would facilitate the comparison of warps, make key aspects of warps easier for the warp designer to understand, and allow a warp designer to increase his or her efficiency by more readily integrating existing solutions for particular aspects of a warp. Ideally, such a general solution technique would not compromise on the warp designer""s ability to achieve the same warp results as could be obtained with conventional solutions. Still further, it would be desirable for such a general solution technique to enable warp results unobtainable with conventional solutions. Also it would be desirable for such a general solution technique to modify existing warping techniques to add new functionality. Additionally it would be desirable for such a general solution technique to faciliate analysis of warps for ascertaining desirable mathematical properties.
One such exemplary conventional solution are free form deformations (xe2x80x9cFFDxe2x80x9ds). Typically FFDs are manipulated by editing of positions of control points in a uniform 3-D lattice imposed on a parallelepiped volume. While this technique yields some desirable mathematical properties, it is can often be highly restrictive to a warp designer. For instance, with conventional FFDs, it is not practicable to create a deformation with a rotation effect centered around a single control point. To achieve such an effect with a conventional FFD, a higher resolution control lattice must typically be used; however, this too is undesirable as it complicates the deformation interface over the model. Thus it would be desirable for a warping system to exist that allowed for more complex warping effects to be easily obtained in conjunction with creating results similar to FFD-type warps.
Another exemplary conventional solution are image warps such as those described by Beier and Neely""s, Feature-based image metamorphosis, Computer Graphics (SIGGRAPH ""92 Proceedings) vol. 26, pages 35-42, July 1992. In Beier and Neely""s disclosure, image warps are defined by line-segment features. When two (or more) line segments xe2x80x9csqueezexe2x80x9d a portion of the image, the warped image may exhibit undesirable spatial buckling artifacts. These artifacts arise out of an assumption that the transformation for a line segment feature should not deform the image in a direction perpendicular to the line segment. For a single-segment, this assumption may not lead to undesirable effects, however for more complex warps, spatial buckling can arise. Accordingly it would be advantageous if a warping system were available that could eliminate spatial buckling in feature based image warps.
Still another exemplary conventional technique is the framework taught by Singh and Fume in Wires: A geometric deformation technique, SIGGRAPH ""98 Conference Proceedings, Pages 405-414. ACM SIGGRAPH, Addison Wesely, July 1998. Wires provides an interactive deformation framework for complex geometric models based on a metaphor to a sculptor""s armature, i.e., controllable curves that deform the surface of an graphical object near the curve (a xe2x80x9cwirexe2x80x9d). While the Wires framework provides a useful geometric deformation technique, it also can create buckling and tearing artifacts when a given wire""s reference curve is shaped so that a set of points is equidistant from different parts of the curve that specify competing deformations. Therefore it would be beneficial if a warping technique existed that could provide the functionality of Wires-type techniques but in a way which enabled buckling and tearing artifacts to be eliminated.
Frequently variations on a (typically complex) surface are desired. Direct manipulation of the surface itself may be too time consuming. There are a number of conventional multiresolution editing schemes that provide some capability for efficient surface variation. However the conventional methods do allow adequate flexibility (for instance they often restrict the relationship between the fine surface model, e.g., a vertex mesh, and the control model in terms of topology or mesh connectivity). While some conventional methods do allow control models of arbitrary topology, such methods may only approximate the edited control points (rather than being interpolating). However, interpolating warps frequently can provide a more intuitive user interface. Accordingly a need exists for an interpolating warp that may be used to conveniently deform a more complex surface of arbitrary topology.
Also, warp designers commonly desire to deform a first surface by mapping regions of the first surface to regions of a second surface. For instance, in computer animation, when the first surface is impacted by the second surface, the first surface may be stretched out of shape. Some physics-based systems that implement this behavior do exist, however such systems are frequently inadequate for production of exaggerated or fictional animation effects. Thus it would be helpful for a warping technique to exist that facilitated deformations of surface regions.
In order to provide solutions to these and other objectives, one aspect of the present invention are methods for generating graphical warps or deformations through feature-based transformation of an undeformed model to create a deformed model. An illustrative method includes receiving the undeformed model and a set of feature specifications each of the set of feature specifications including a source feature, a target feature, and related deformation parameters. The set of feature specifications contains elements for controlling the deformation of the undeformed model. An additional part of this illustrative method includes receiving a set of transformations corresponding to the set of feature specifications and for mapping the source feature to the target feature in each of the set of feature specifications, and receiving a set of strength fields corresponding to the set of feature specifications and defined over the undeformed model for scaling the magnitude of each of the set of transformations, establishing a set of scaled transformations. The illustrative method also includes receiving a set of weighting fields corresponding to the set of feature specifications and defined over the undeformed model for determining the relative influence of the set of scaled transformations; computing a sum of the set of scaled transformations, weighted by the set of weighting fields, creating a deforming function for deforming the undeformed model to generate the deformed model; and returning the deformed model.
In a variation of the illustrative method, at least one of the set of feature specifications is continuous and has corresponding parameterized strength field, transformation, and weighting field. In this variation, the illustrative method also includes receiving a sampling function for discretizing the transformation and sampling strength and weighting fields and computing a discretized transformation, a sampled strength field, and a sampled weighting field with the sampling function. In this instance, the step of computing a sum of the set of scaled transformations employs the discretized transformation, the sampled strength field, and the sampled weighting field.
Still further, the set of feature specifications, the set of transformations, the set of strength fields, the set of weighting fields, and the sampling function can be received by a combined function that computes the discretized transformation, the sampled strength field, and the sampled weighting field.
It should be noted that the present invention is operable with geometric deformations in a general manner. In particular, the present invention is not limited to feature-based deformations, although it may obtain particular benefits with feature-based deformations.
The illustrative method operates with a wide variety of features and conveniently generates many useful deformations. In one version, the set of feature specifications includes a plurality of line segment features; the set of transformations corresponding to the plurality of line segment features map source coordinate frames to target coordinate frames; and the set of weighting fields corresponding to the plurality of line segment features fall off with distance. In some instances, the set of weighting fields give influence to line segment features in the plurality of line segment features in relation to their length. In some instances, the source coordinate frames include a constrained basis vector and an unconstrained basis vector and the unconstrained basis vector is selected responsive to a weighted sum of the vectors perpendicular to the constrained basis vector for each of said target coordinate frames.
In another version, the set of feature specifications includes control points in an at least two dimensional lattice. The at least two dimensional lattice has an associated local coordinate system, and the set of weighting fields corresponding to the control points include Bernstein polynomials with their arguments as points of the undeformed model represented in the local coordinate system. In a variation, oriented points are used.
In yet another version, at least one of said set of feature specifications includes a source curve and a target curve. Here, corresponding members of the set of parameterized transformations include a composition of a translation from points along the source curve to corresponding points along the target curve, a rotation taking the tangent at the points along the source curve to the tangent at the points along the target curve, and a scale centered at the points along the source curve. In addition, corresponding members of said set of strength fields include a falloff function having a domain and a range and monotonically decreasing over the range. Over at least a portion of the domain (and sometimes over the entirety), arguments of the falloff function include a distance between elements of the undeformed model and point along the source curve and a rate of falloff for the distance. Also, corresponding members of the set of weighting fields include a scaled displacement function having a domain and a range, wherein for at least a portion of the domain the scaled displacement function includes a power of the displacement of elements of said undeformed model by the corresponding members of said set of transformations.
In another version, the undeformed model includes control vertices of a fine detail model. In this instance, and at least one of the set of feature specifications may include a source position and a target position of one or more vertices of a coarse deformation mesh. The coarse deformation mesh may be configured so that deformation of the fine surface model may be obtained by deformation of the coarse deformation mesh. In addition, the set of feature specifications includes one or more sets of edges incident on the one or more vertices.
In still another version, the undeformed model includes control vertices of a surface for deformation. No representation of the surface is essential and any point valued model could be used. Source and target features are surface regions (surfaces or parts thereof) described as aa function that evaluates to tuples of a point on the feature and a vector normal to the point on the source or target surface region. The source and target suface regions need not be subsets of the suface model. Corresponding members of the set of transformations include a composition of a translation mapping points on the source region of the surface to points on the target region of the surface, and a rotation taking the vector normal to the points on the source region to the vector normal to the points on the target region of the surface. In a variation, corresponding members of the set of strength fields localize the effect of the set of transformations around the source surface region. In addition, corresponding members of the set of weighting fields decrease monotonically with corresponding members of said set of strength fields and the set of weighting fields decrease responsive to (a) a distance between control vertices of the surface for deformation and said point on said surface, (b) a range for limiting the region of the weighting field, and (c) a rate for controlling the rate of decrease of the weighting field.
Another aspect of the invention is computing machinery configured to carrying on the methods in accordance with the invention including, for instance, the above-described methods. Still another aspect is a computer program product including a computer readable medium having computer program code encoded thereon able to configure computing machinery to carry on methods in accordance with the invention.